Giả sử C là một lớp độ phức tạp gồm các bài toán giải được bằng máy Turing ngẫu nhiên dùng bộ nhớ lôgarit sao cho máy không bao giờ chấp nhận sai nhưng được phép từ chối sai với xác suất 1/3. Hằng số 1/3 là tùy ý, bất kì số x nào thỏa mãn 0 ≤ x < 1/2 đều chấp nhận được.

Hóa ra C = NL. Có thể thấy C, không như lớp L, không bị giới hạn bởi thời gian đa thức, bởi vì mặc dù nó chỉ có một số đa thức các trạng thái, nó cũng có thể dùng sự ngẫu nhiên để thoát ra một vòng lặp vô hạn. Nếu giới hạn trong thời gian đa thức, ta nhận được lớp RL nằm trong NL nhưng không biết có bằng hay không.

Sau đây là một chứng minh đơn giản cho C=NL. Rõ ràng C nằm trong NL do:

• Nếu dữ liệu vào không nằm trong ngôn ngữ, cả hai đều từ chối tất cả các đường tính toán
• Nếu dữ liệu vào nằm trong ngôn ngữ, thuật toán NL chấp nhận ít nhất một đường tính toán trong khi thuật toán C chấp nhận 2/3 số đường tính toán.

Để chứng minh NL nằm trong C, ta lấy một thuật toán NL và chọn một đường tính toán bất kì có độ dài n, và lặp lại 2n lần. Do không có đường tính toán nào có độ dài lớn hơn n, và có tất cả 2n đường tính toán, xác suất tìm được một đường được chấp nhận là cao (chặn dưới bởi một hằng số).

Có một vấn đề là ta không có đủ bộ nhớ để đếm đến 2. Để vượt qua trở ngại này, ta sử dụng một thuật toán đếm ngẫu nhiên: tung n đồng xu và dừng khi tất cả đều ngửa. Do sự kiện này xảy ra với xác suất 2-n, trung bình thuật toán lặp lại 2n lần trước khi dừng. Do chỉ cần đếm số đồng xu ngửa, ta chỉ cần bộ nhớ lôgarit.

Do đó, khi ta chỉ quan tâm đến lượng bộ nhớ, trong trường hợp này, có vẻ như sự ngẫu nhiên và không đơn định là mạnh ngang nhau.